package leetcode.year2021.month10;

//124. 二叉树中的最大路径和
public class _27_01MaxPathSum124 {
  /**
   * 首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
   *
   * 具体而言，该函数的计算如下。
   *
   * 空节点的最大贡献值等于 00。
   *
   * 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）
   *
   * @param root
   * @return
   */
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    int ans = 0;
    maxGain(root);
    return maxSum;
  }

  public int maxGain(TreeNode root){
    int ans = 0;
    if (root == null){
      return ans;
    }
    ans += root.val;

    int maxLeft = Math.max(maxGain(root.left),0);
    int maxRight = Math.max(maxGain(root.right),0);

    ans += maxLeft;
    ans += maxRight;

    maxSum = Math.max(maxSum, ans);
    return root.val + Math.max(maxLeft,maxRight);
  }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

  /**
   * 124. 二叉树中的最大路径和
   * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
   *
   * 路径和 是路径中各节点值的总和。
   *
   * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
   *
   *
   *
   * 示例 1：
   *
   *
   * 输入：root = [1,2,3]
   * 输出：6
   * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
   * 示例 2：
   *
   *
   * 输入：root = [-10,9,20,null,null,15,7]
   * 输出：42
   * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
   *
   *
   * 提示：
   *
   * 树中节点数目范围是 [1, 3 * 104]
   * -1000 <= Node.val <= 1000
   */
}
